function solveNQueens(n: number): string[][] {
  const ans: string[][] = [];
  const local: number[][] = [];
  const used: boolean[] = new Array(n).fill(false);
  const usedPlus: Map<number, boolean> = new Map();
  const usedMinus: Map<number, boolean> = new Map();
  const p: number[] = [];
  dfs(0);
  for (let l of local) {
    const s = new Array(n).fill('').map(() => new Array(n).fill('.').join(''));
    for (let row = 0; row < n; row++) {
      s[row] = s[row].slice(0, l[row]) + 'Q' + s[row].slice(l[row] + 1);
    }
    ans.push([...s]);
  }
  return ans;
  function dfs(row: number) {
    if (row === n) {
      local.push([...p]);
      return;
    }
    for (let col = 0; col < n; col++) {
      if (!used[col] && !usedPlus.get(row + col) && !usedMinus.get(row - col)) {
        p.push(col);
        used[col] = true;
        usedPlus.set(row + col, true);
        usedMinus.set(row - col, true);
        dfs(row + 1);
        used[col] = false;
        usedPlus.set(row + col, false);
        usedMinus.set(row - col, false);
        p.pop();
      }
    }
  }
};